package com.sheng.leetcode.year2025.month09.day03;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2025/9/18
 * <p>
 * 3027. 人员站位的方案数 II<p>
 * <p>
 * 给你一个  n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。<p>
 * 我们定义 x 轴的正方向为 右 （x 轴递增的方向），x 轴的负方向为 左 （x 轴递减的方向）。<p>
 * 类似的，我们定义 y 轴的正方向为 上 （y 轴递增的方向），y 轴的负方向为 下 （y 轴递减的方向）。<p>
 * 你需要安排这 n 个人的站位，这 n 个人中包括 Alice 和 Bob 。你需要确保每个点处 恰好 有 一个 人。<p>
 * 同时，Alice 想跟 Bob 单独玩耍，所以 Alice 会以 Alice 的坐标为 左上角 ，<p>
 * Bob 的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能 不 包含任何区域，也就是说围栏可能是一条线段）。<p>
 * 如果围栏的 内部 或者 边缘 上有任何其他人，Alice 都会难过。<p>
 * 请你在确保 Alice 不会 难过的前提下，返回 Alice 和 Bob 可以选择的 点对 数目。<p>
 * 注意，Alice 建立的围栏必须确保 Alice 的位置是矩形的左上角，Bob 的位置是矩形的右下角。<p>
 * 比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，<p>
 * 给定下图的两个输入，Alice 都不能建立围栏，原因如下：<p>
 * 图一中，Alice 在 (3, 3) 且 Bob 在 (1, 1) ，Alice 的位置不是左上角且 Bob 的位置不是右下角。<p>
 * 图二中，Alice 在 (1, 3) 且 Bob 在 (1, 1)（如图所示，用矩形代替线条），Bob 的位置不是在围栏的右下角。<p>
 * <p>
 * 示例 1：<p>
 * 输入：points = [[1,1],[2,2],[3,3]]<p>
 * 输出：0<p>
 * 解释：没有办法可以让 Alice 的围栏以 Alice 的位置为左上角且 Bob 的位置为右下角。所以我们返回 0 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：points = [[6,2],[4,4],[2,6]]<p>
 * 输出：2<p>
 * 解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：<p>
 * - Alice 站在 (4, 4) ，Bob 站在 (6, 2) 。<p>
 * - Alice 站在 (2, 6) ，Bob 站在 (4, 4) 。<p>
 * 不能安排 Alice 站在 (2, 6) 且 Bob 站在 (6, 2) ，因为站在 (4, 4) 的人处于围栏内。<p>
 * <p>
 * 示例 3：<p>
 * 输入：points = [[3,1],[1,3],[1,1]]<p>
 * 输出：2<p>
 * 解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：<p>
 * - Alice 站在 (1, 1) ，Bob 站在 (3, 1) 。<p>
 * - Alice 站在 (1, 3) ，Bob 站在 (1, 1) 。<p>
 * 不能安排 Alice 站在 (1, 3) 且 Bob 站在 (3, 1) ，因为站在 (1, 1) 的人处于围栏内。<p>
 * 注意围栏是可以不包含任何面积的，上图中第一和第二个围栏都是合法的。<p>
 * <p>
 * 提示：<p>
 * 2 <= n <= 1000<p>
 * points[i].length == 2<p>
 * -10^9 <= points[i][0], points[i][1] <= 10^9<p>
 * points[i] 点对两两不同。<p>
 */
public class LeetCode3027 {

    @Test
    public void test() {
//        int[][] points = {{1, 1}, {2, 2}, {3, 3}};
//        int[][] points = {{6, 2}, {4, 4}, {2, 6}};
//        int[][] points = {{3, 1}, {1, 3}, {1, 1}};
        int[][] points = {{0, 1}, {0, 2}, {2, 5}, {3, 0}};
        System.out.println(new Solution().numberOfPairs(points));
    }
}

class Solution {
    public int numberOfPairs(int[][] points) {
        /**
         * 存在 (A, B) 意味着数组 points 内首先得存在 [xi, yi] 和 [xj, yj] 满足 xi < xj && yi >= yj
         * 在这个条件下，要求没有其他点，意味着数组内的其他元素 [x, y] 需要 x < xi < xj < x || y < yj <= yi < y 的其中任意一个条件
         * 即，横向或者竖向任意一个方向上，满足，小于最小值，大于最大值，即可
         * 或者说循环数组，查询到有 xi <= x <= xj && yj <= y <= yi 时， (A, B) 不满足要求
         * 注意两个点形成一条线的情况是合法的
         */
        // x 按照从大道小排序，相等的情况下 y 按照从小到大排序
        Arrays.sort(points, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
        int n = points.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            next:
            for (int j = n - 1; j > i; j--) {
                // 判断两个点是否满足 (A, B) 的条件要求。points[i] 点对两两不同
                if (points[i][1] <= points[j][1]) {
                    // 满足要求点位要求，判断是否存在其他点位
                    for (int k = i + 1; k < j; k++) {
                        if (points[k][1] <= points[j][1] && points[k][1] >= points[i][1]) {
                            continue next;
                        }
                    }
                    ans++;
                }
            }
        }
        return ans;
    }
}
